class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # 摩尔投票，同归于尽
        # 还可以哈希或排序取中
        vote, x = 0, 0
        for num in nums:
            if vote == 0:
                x = num
            if num == x:
                vote += 1
            else:
                vote -= 1
        return x